package JZOffer;

/**
 * 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
 * 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，
 * 使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
 * **/

//方案一  辅助数组
//    遍历两边nums，第一遍遍历奇数，放入res数组
//    第二遍遍历偶数，添加到res数组中
//    复杂度分析：
//            时间复杂度：O(n)
//            空间复杂度：O(n)
class Solution21_1 {
    public int[] exchange(int[] nums) {
        //定义数组res
        int[] res = new int[nums.length];
        int index = 0;
        for (int num : nums){
            if (num % 2 == 1){
                res[index++] = num;
            }
        }
        for (int num : nums){
            if (num % 2 ==0){
                res[index++] = num;
            }
        }
        return res;
    }
}

//方案二 头尾双指针

//left指向数组头，right指向数组尾
//        left右移直到指向了偶数
//        right左移直到指向了奇数
//        如果left此时已经大于right，break结束循环
//        交换left和right所指数字
//        继续以上步骤，直到left > right
//        时间复杂度：O(n)
//        空间复杂度：O(1)

class Solution21_2 {
    public int[] exchange(int[] nums) {
        int left = 0, right = nums.length - 1;
        while(left <= right){
            while(left <= right && nums[left] % 2 == 1)
                left++;
            while(left <= right && nums[right] % 2 == 0)
                right--;
            if(left > right)
                break;
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
        }
        return nums;
    }
}

//方案三    快慢双指针法
//        slow和fast都从数组的头部开始遍历
//        fast正常一步一步右移
//        如果fast遇到了奇数，和slow位置的数字互换，slow++，fast++
//        如果fast没有遇到奇数，继续右移，fast++
//        fast遍历到末尾时结束遍历
//
//        时间复杂度：O(n)
//        空间复杂度：O(1)

class Solution21_3 {
    public int[] exchange(int[] nums){
        int slow = 0, fast = 0;
        while (fast < nums.length){
            if (nums[fast] % 2 == 1){
                int temp = nums[slow];
                nums[slow] = nums[fast];
                nums[fast] = temp;
                slow++;
            }
            fast++;
         }
        return nums;
    }
}